The field of digital image editing, manipulation, and enhancement is evolving to contain three-dimensional (3D) scene structure understanding. Under a pinhole camera model, a set of parallel lines in a 3D scene is projected to a set of concurrent lines which meet at a single point, known as a vanishing point (VP). Each VP is associated with a unique 3D orientation, and hence can provide valuable information on the 3D structure of the scene. VPs are used for a variety of vision tasks such as camera calibration, perspective rectification, scene reconstruction and more. For example, knowledge of the location of a VP is required in applications such as reliably planting objects in images uploaded via the internet: where ‘reliably’ typically means ensuring accurate scaling. Techniques for determining VPs in images are well-known and typically rely on finding straight lines in the images, and projecting those lines to find locations, on the image plane, where the projected lines intersect. Intersections may be within the image area or outside of the image area, depending on the nature of the image. Known techniques can fail in a variety of cases where straight features are either not present or are too faint or blurred to be detected credibly. In addition, the accuracy and credibility of current VP estimation methods can deteriorate quickly in relatively low resolution images, due to feature blurring and line digitization artifacts. Finally, the computational complexity of existing techniques is relatively high and scales not only with image size but also with the density of straight line segments in the image. Hence it is hard to design a general solution with a good control of the trade-off between estimation accuracy and speed.